class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* tem = head;
        Node* Newhead = nullptr;
        Node* f = nullptr;
        Node* s = nullptr;
        int count = 0;
        int count1 = 0;
        std::unordered_map<Node*, int> guide1;
        std::unordered_map<int, Node*> guide2;
        std::unordered_map<Node*, int> guide3;
        while (tem)
        {
            s = new Node(tem->val);
            if (Newhead == nullptr)
            {
                Newhead = s;
                f = s;
                guide1.insert({ tem,count++ });
                guide2.insert({ count1++,s });
                s = s->next;
                tem = tem->next;
                continue;
            }
            f->next = s;
            f = s;
            guide2.insert({ count1++,s });
            s = s->next;
            guide1.insert({ tem,count++ });
            tem = tem->next;
        }
        tem = head;
        s = Newhead;
        guide1.insert({ nullptr,INT_MAX });
        guide2.insert({ INT_MAX,nullptr });
        while (tem)
        {
            guide3.insert({ s,guide1[tem->random] });
            tem = tem->next;
            s = s->next;
        }
        s = Newhead;
        while (s)
        {
            s->random = guide2[guide3[s]];
            s = s->next;
        }
        return Newhead;
    }
};